import java.util.List;

/**
 * Created by L.jp
 * Description:给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * User: 86189
 * Date: 2022-02-13
 * Time: 11:51
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      
}
public class Solution {
    /*  思路：反转链表其实就是修改指向，所以我们不需要重新构造一个链表，只需要在原来的基础上修改链表指向就可以了
       比如原来链表是：1->2->3->4->5->null,翻转后变成了：null<-1<-2<-3<-4<-5,这就是修改指向，把原来的头变成了尾
       我们可以定义一个新的头指针newhead=null，这个头指针不仅是最后的新头节点也起到了前驱节点作用
       定义cur指针指向当前节点，一开始第一个节点后继本来指向2，翻转后就是第一个节点后继变成了newhead,此时是null
       然后让newhead=cur往后走，继续做下一个节点的前驱，然后cur也往下走，继续翻转，就这样循环
    * */
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        //迭代版本：
        ListNode newHead=null;//一开始作为新链表的尾巴，即是最后的头结点，也是前驱节点作用
        ListNode cur=head;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=newHead;//改变指向，指向前驱节点
            newHead=cur;//作为下一次的前驱节点
            //cur = cur.next;//不能不保存当前节点的下一个节点，因为修改指向了，当前节点的下一个节点变成了前驱结点，
            // 如果这样写的话就又跳回去了，所以进循环之前需要先保存当前节点的下一个节点
            cur=next;//这样才能实现cur节点往下走
        }
        return newHead;
        
    }

}
